The performance of today's very large scale integrated circuits is improved by employing combinations of increased operating frequencies and increased circuit complexity as well as by decreasing on-chip feature dimensions and supply voltages. The consequential increase in the resistive nature of the power supply network, easily one of the most critical networks in the circuit, results in an increased susceptibility to serious problems such as electromigration, overheating, and drop in voltage levels in power rails toward the center of the integrated circuit ("voltage droop"). These problems have been well known in the industry to adversely effect the reliability and operation of the circuit. For these reasons, reliability verification prior to fabrication is recognized as an essential stage in the design process.
A consequence of increasing size and complexity in integrated circuits is that existing reliability verification tools are literally overwhelmed when presented with some of today's very large scale integrated circuits.
In the case of verifying power networks, reliability verification tools typically comprise computer programs for circuit simulation. These circuit simulation tools operate on a model of the power network as a description of hierarchical resistive circuits. Hierarchical resistive circuits are characterizations of a circuit as networks of resistances connected by nodes. As is known in the art, such networks are connected to voltage supplies, or source voltages, and in operation have particular currents flowing through each resistance and certain voltages at each node. The currents are known as branch currents, where a branch connects two nodes, and the voltages are known as node voltages. Hierarchical resistive networks are divided into levels of hierarchy, usually on the basis of particular functions of subcircuits. The subcircuits are known as macro circuits or macros. For example, a macro circuit with the function of a comparator would contain within it, at lower level(s) of hierarchy, the circuits representing the logic gates that make up the comparator. The circuit simulation tools simulate the behavior of the model circuit under actual source voltages with the object of obtaining branch currents and node voltages. Once branch currents and node voltages are obtained it is possible to determine power levels at various area in the circuit using well known equations. Thus, it can be determined if there will be overheating problems, voltage droop problems or electromigration problems. In this way, a circuit designer tries to obtain enough information to adjust the design of the circuit before the cost of fabrication is incurred.
Current simulation tools simulate the behavior of the resistive circuit only by removing all hierarchical information (flattening the circuit) and solving for node voltages and branch currents by constructing and solving a matrix according to well known circuit analysis techniques. As circuits become larger and more complex, however, the matrix becomes prohibitively large to store and solve. Very large matrices require not only large amounts of storage space but also long periods of time to solve. For example, a circuit with 1000 nodes (a modest number in comparison to the total number of nodes in a very large integrated circuit), the size of a full admittance matrix, such as is commonly used with current simulation tools, is one million numbers. It is currently possible, according to known techniques, to partition the flattened circuit into more manageable chunks. This partitioning, however, is very dependent on circuit topology and suffers from other disadvantages, such as loss of original hierarchical information, as further described below.
Loss of original hierarchical information is a serious disadvantage of present simulation tools. For instance, when existing simulation tools flatten the hierarchical resistive circuit, no hierarchical information is saved. For this reason, when voltage droop is discovered at a particular node or electromigration is discovered at a particular resistance, even though the resistance or node may be eventually identified, its original hierarchical name or identifier has been lost and can only be recovered through the development and use of software tools designed for the purpose. This is costly in terms of time and effort. Very large integrated circuits are commonly designed using teams of designers, each working on different parts of the integrated circuit. When problems that require re-design, such as voltage droop or electromigration, are discovered the designer or team of designers that owns the part of the overall integrated circuit must be identified. It may be difficult to identify the owners of the problematic part of the circuit when original hierarchical information is no longer available.
Another significant limitation of existing simulation tools is their inability to identify and handle floating nodes before simulation actually takes place. This is significant because when floating nodes exist in the circuit (that is, nodes which are not connected to a reference voltage via a direct current (DC) path) current simulators fail completely. In addition, such a failure may not be immediately traceable to the floating node or nodes. Floating nodes are a possible cause of, for example, anomalous results of timing simulation. Because floating nodes are such a problem, it is commonly necessary to write scripts to try to identify floating nodes before they cause testing to fail. Although floating nodes are undesirable because they can introduce capacitive effects that seriously affect integrated circuit performance, they are commonly introduced by accident in the design process.
Another disadvantage of existing simulation tools is their inability to efficiently and accurately handle short circuits in the resistive circuit. Typically, existing simulation tools identify shorts and handle them by inserting an extremely small resistance in the place of each short. This method of handling shorts has at least two problems. First, the resistance that is used in these methods does not accurately reflect the resistance in a short circuit. Short circuits have zero resistance and zero voltage. For instance, because voltages are arrived at by dividing current by resistance, a very large, but inaccurate, current will be assigned to short circuits. Second, because the typical method of obtaining node voltages and branch currents for resistive circuits is to solve a matrix, the extremely small resistance numbers will cause the matrix to be ill conditioned, thus introducing potentially significant numerical errors.
The present invention overcomes the problems described above by employing efficient recursive techniques that avoid the solution of large matrices, handle shorts and floating nodes effectively, and retain hierarchical information in a final solution of an entire resistive circuit.